\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

\title{二叉树和节点的逻辑设计}



\author{赖心怡 \\  医学实验班(临床医学八年制) 3210100987}

\begin{document}

\maketitle


\section{项目设计思路}
很多数据结构都是一些节点的集合,例如非空的二叉树 $t$ 由根节点 $r$ 以及 $0$ 个或多个非空子树 $T_1$ , $T_2$ , ..., $T_k$ 组成, 平衡树是在二叉树的基础上保持平衡条件, 即保证树的深度是 $O(log N)$, 两者之间存在继承关系.

因此在设计 \verb|BinaryTree| 和 \verb|Node| 类时, 先考虑 \verb|Node| 作为基类, 有成员变量 $element$ 及实现赋值和返回值功能的函数, \verb|BinaryNode| 类作为 \verb|Node|的派生类添加指向两子树的指针变量, \verb|AvlNode| 类作为 \verb|Node| 的派生类添加指向两子树的指针变量和当前节点深度. \verb|AvlTree| 为 基类\verb|BinarySearchTree|的派生类,具体实现如下UML图所示:
\begin{figure}[htpb]
	\center{\includegraphics{figure1.png}}
	\caption{设计思路}
	\label{figure1}
\end{figure}

\section{测试说明}
(未在头文件中实现具体函数因此未编译)

定义 \verb|Node| 类节点 \verb|n| 并进行赋值, 返回值操作.以下代码测试 \verb|BinarySearchTree| 和 \verb|AvlTree| 两类, 若能通过编译且输出正确结果证明设计合理.
\begin{verbatim}
	BinarySearchTree<int> a;
        AvlTree<int> b;
        for ( i = 10; i > 0; i --){
               a.push_back(i);
	       b.push_back(i);
        }
        printTree(a); printTree(b);
\end{verbatim}

\end{document}
